/*
解题思路：
 1. 从后序遍历结果中获取到树的根节点，注意：后序遍历规则：左子树、右子树、根节点，因此应该从后往前获     取根节点
 2. 在中序遍历结果中确定根节点的位置，按照该位置将中序遍历结果分为两部分
    右半部分是根节点的右子树，递归创建根节点的右子树---->注意先要还原根的右子树
    左半部分是根节点的左子树，递归创建根节点的左子树
*/
class Solution4 {
    int index = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = postorder.length-1;
        return buildTree(postorder, inorder, 0, inorder.length);
    }


    // index不断在后序遍历中找根节点，每次找完之后，根据找到的根节点将中序遍历分成左右两部分，左侧为根的左子树，右侧为根的右子树
    // 注意：与前序中序还原二叉树不同的是，此次需要先还原右子树

    private TreeNode buildTree(int[] postorder, int[] inorder, int left, int right){
        if(left >= right){
            return null;
        }
        // 创建跟节点
        TreeNode root = new TreeNode(postorder[index]);
        // 在中序遍历结果中找到根的位置
        int rootIdx = left;
        while(rootIdx < right){
            if(inorder[rootIdx] == postorder[index])
                break;

            rootIdx++;
        }
        index--;
        //[rootIdx+1, right): 右子树中的所有节点
        // 递归创建根的右子树
        root.right = buildTree(postorder, inorder, rootIdx+1, right);
        //[left, rootIdx)：左子树中的所有节点
        // 递归创建根的左子树
        root.left = buildTree(postorder, inorder, left, rootIdx);
        return root;
    }
}